package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked
 * 题解：https://leetcode.cn/problems/longest-consecutive-sequence/solutions/1453487/by-lfool-jdy4/?envType=study-plan-v2&envId=top-100-liked
 * 并查集实现
 * 通过
 *
 * @author yulongTian
 * @create 2024-05-24 16:01
 */
public class Test03_01 {

    public static void main(String[] args) {
//        System.out.println(new Test03_01().longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
        System.out.println(new Test03_01().longestConsecutive(new int[]{}));
    }

    public int longestConsecutive(int[] nums) {
        UF uf = new UF(nums.length);
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) {
                continue;
            }
            if (hashMap.containsKey(nums[i] - 1)) {
                uf.union(i, hashMap.get(nums[i] - 1));
            }
            if (hashMap.containsKey(nums[i] + 1)) {
                uf.union(i, hashMap.get(nums[i] + 1));
            }
            hashMap.put(nums[i], i);

        }

        return uf.getMaxConnectSize();
    }

    class UF {
        private int[] parent;
        private int count;
        private int[] size;

        public UF(int n) {
            this.count = n;
            this.parent = new int[n];
            this.size = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
                this.size[i] = 1;
            }
        }

        /* 将 p 和 q 连接 */
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;

            // 平衡性优化
            if (size[rootP] >= size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
            // 有合并，连通分量就相减
            count--;
        }

        /* 判断 p 和 q 是否连通 */
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        /* 返回图中有多少个连通分量 */
        public int count() {
            return count;
        }

        /* 返回当前节点的根节点 */
        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        private int getMaxConnectSize() {
            int maxSize = 0;
            for (int i = 0; i < parent.length; i++) {
                if (i == parent[i]) {
                    maxSize = Math.max(maxSize, size[i]);
                }
            }
            return maxSize;
        }
    }


}
